#include <cstdint>

namespace rb_tree
{
    static const uint8_t RED = 1;
    static const uint8_t BLACK = 0;

    template <typename T>
    struct rb_node
    {
        rb_node();
        ~rb_node();

        rb_node<T> *sibling();

        rb_node<T> *lchild_, *rchild_, *parent_;
        uint8_t color_;
        T *data_;
    };

    template <typename T>
    struct rb_tree
    {
        rb_tree();
        ~rb_tree();

        void rotate_left(rb_node<T> *);
        void rotate_right(rb_node<T> *);

        void del_tree(rb_node<T> *);
        rb_node<T> *search(rb_node<T> *, rb_node<T> *&);
        void *insert(rb_node<T> *);

        typedef int (*cmp)(rb_node<T> *, rb_node<T> *);
        rb_node<T> *root_;
        cmp cmp_func;
    };
} // namespace rb_tree
